public class AVLTree {
    static class TreeNode{
     private int val ;
     private TreeNode left ;
     private TreeNode right ;
     private TreeNode parent ;
     private int bf ;
     public TreeNode(int val){
         this.val =val ;
     }
    }
    private TreeNode root ;

    public void insert(int val){
        TreeNode node = new TreeNode(val);
        if(this.root == null){
            this.root = node ;
        }
        TreeNode cur = this.root ;
        TreeNode parent = null ;
        while (cur != null){
            if(cur.val < val){
             parent = cur ;
             cur = cur.right;
            }else{
                parent = cur ;
                cur = cur.left;
            }
        }
        if(parent.val > val){
            parent.left = node ;
        }else{
            parent.right = node ;
        }
        cur = node ;
        // 判断平衡因子, 是否有超
        while (parent != null){    //判断条件, 一直往上,直到判断完所以
            // 看cur在左还是右, 右++ , 左--
            if(cur == parent.left){
                parent.bf --;
            }else {
                parent.bf ++ ;
            }
            // 判断parent的平衡因子
            if(parent.bf == 0){
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                // 继续往上
                cur = parent ;
                parent = cur.parent ;
            }else{
                // 找到 平衡因子为 2或-2的地方 ;
                if(parent.bf == 2){        // 右子树高了
                  if(cur.bf == 1){
                      // 新节点在 cur的右子 , 进行左单旋
                     rotateLeft(parent);
                  }else{
                        // 右左双旋
                      rotateRL(parent);
                  }
                }else{               // bf == -2  左子树超了
                    if(cur.bf == 1){
                        // 左右双旋
                        rotateLR(parent);

                    }else{
                        // cur.bf ==-1 , 进行右单旋
                        rotateRight(parent);

                    }

                }
                // 把 平衡因子 为2 的, 进行旋转后,此时树已经平衡了,可以停止循环
                break;
            }

        }

    }

    /**
     * 左右双旋
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left ;
        TreeNode subLR = subL.right ;
        int bf = subLR.bf ;
        rotateLeft(subL);
        rotateRight(parent);
        if(bf == 1){
            subL.bf = -1;
            parent.bf = 0 ;
            subLR.bf = 0 ;
        }else{
            subL.bf = 0 ;
            subLR.bf = 0 ;
            parent.bf = 1 ;
        }
    }

    // 右左双旋


    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right ;
        TreeNode subRL = subR.left;
        int bf = subRL.bf ;
        // 右旋
        rotateRight(subR);
        rotateLeft(parent);
        if(bf == 1){
            subRL.bf = 0;
            parent.bf = -1 ;
            subR .bf = 0 ;
        }else{
            parent.bf = 0 ;
            subRL.bf = 0 ;
            subR.bf = 1 ;
        }
    }



    // 左旋
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right ;
        TreeNode subRL = subR.left ;
        TreeNode pParent = parent.parent ;

        parent.right = subRL ;
        if(subRL != null){
            subRL .parent = parent ;
        }
        subR.left = parent ;
        //判断 旋转后 subR的parent应该如何
        if(parent == this.root){
            this.root = subR ;
            this.root.parent = null ;
        }else{
            // 判断parent在右子还是左子
            if(parent == pParent.left){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
        }
        parent.parent = subR ;
        parent.bf = 0 ;
        subR.bf = 0 ;

    }

    // 右旋
    private void rotateRight(TreeNode parent){
         TreeNode subL = parent.left ;
         TreeNode subLR = subL.right ;

         parent.left = subLR ;
         subL.right = parent ;
         TreeNode pParent = parent.parent ;
         // 处理subR
        if(subLR != null){
            subLR.parent = parent ;
        }
         //处理parent, 处理后, parent的父亲才能指向 subL
        // parent是root
        if(this.root == parent){
           this.root = subL ;
            this.root.parent = null;
        }else{
            // parent 不是root1
            // parent 是左子 还是右子 ;
            if(parent == pParent.left){
                pParent.left = subL ;
            }else{
                pParent.right = subL ;
            }
            subL.parent = pParent ;
        }
        parent.parent = subL ;

        // 旋转完了,修改 subL 和 parent的平衡因子 ;
        subL.bf = 0 ;
        parent.bf = 0 ;

    }


}
